package targetToOffer.nintehDay;

/**
 * @author Godc
 * @description
 */
public class CuttingRope {
    public static void main(String[] args) {
        XSolution s = new XSolution();
        s.bspiralOrder(new int[][]{});
    }
}
class Solution {
    public int cuttingRope(int n) {
        if(n==2) return 1;
        // dp表示长度为i的绳子的最大成绩
        int[] dp = new int[n+1];
        dp[2] = 1;
        for(int i  = 3;i<n+1;i++){
            // 内循环:先减掉一段，长度为j，剩下的i-j可以减也可以不减
            // 取两者最大值
            // 从2开始，因为剪掉长度为1对乘积没有贡献
            for(int j = 2;j<i;j++){
                dp[i] = Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]));
            }
        }
        return dp[n];
    }

    /***
     * 数论解法
     * @param n
     * @return
     */
    public int cuttingRope1(int n){
        // 结论：1.当分成的段数相同时，成绩最大2.最优的字段长度为3
        // 1.将绳子尽可能地全部分成长度为3地字段，最后剩下的长度可能为0，1，2
        // 2.如果剩下地为2，不能再分
        // 3.若最后一段绳子长度为 1 ；则应把一份 3+1替换为2+2，因为 2×2>3×1
        // 所以n = 3*a+b,
        // 1.如果b=0,返回3^a
        // 2.如果b=1，返回3^a-1*4
        // 3.如果a=2,返回3^a*2
        if(n<=3) return n-1;// 题目中说明必须裁一刀
        int a = n / 3,b=n%3;
        if(b==0) return (int)Math.pow(3,a);
        else if(b==1) return (int)Math.pow(3,a-1)*4;
        else return (int)Math.pow(3,a)*2;
    }
}
class HardSolution {
    public int cuttingRope(int n) {
        if(n<=3) return n-1;
        int a = n/3,b = n%3;
        if(b==0) return (int)quickPow(3,a);
        else if(b==1) return (int)quickPow(3,a-1)*4;
        else return (int)quickPow(3,a)*2;
    }
    public long quickPow(int x,int n){
        if(n==0) return 1;
        long half = quickPow(x,n/2);
        if(n%2==0) return half*half;
        else return half*half*x;
    }
}
class XSolution {
    public int[]bspiralOrder(int[][] matrix) {
        int l = 0,r = matrix.length-1,t = 0,b = matrix[0].length-1,x = 0;
        int[] res = new int[(r+1)*(b+1)];
        while(true){
            for(int i = l;i<=r;i++) res[x++] = matrix[t][i];
            if(++t>b) break;
            for(int i = t;i<=b;i++) res[x++] = matrix[i][r];
            if(--r<l) break;
            for(int i = r;i>=0;i--) res[x++] = matrix[b][i];
            if(--b<t) break;
            for(int i = b;i>=0;i--) res[x++] = matrix[i][l];
            if(++l>r) break;
        }
        return res;
    }
}